package com.kevin.Code.TwoPointer;

import scala.Int;

import java.util.Arrays;

/**
 * @author Vinlee Xiao
 * @Classname ThreeSumClosest
 * @Description Leetcode 16 最接近的三数之和 中等难度 思路类似于Leetcode 15 三数之和
 * @Date 2021/10/25 20:05
 * @Version 1.0
 */
public class ThreeSumClosest {

    /**
     * 双指针的思路
     *
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {

        int len = nums.length;

        if (len < 3) {
            return 0;
        }
        int bestNum = 200000;
        Arrays.sort(nums);

        for (int i = 0; i < len; i++) {

            //避免重复 进行优化
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            //左边界和右边界
            int left = i + 1;
            int right = len - 1;
            //双指针
            while (left < right) {
                //三个数之和
                int obj = nums[i] + nums[left] + nums[right];
                if (obj == target) {
                    return target;
                } else if (Math.abs(obj - target) < Math.abs(bestNum - target)) {
                    bestNum = obj;
                }

                //如果数大于target右指针向左移动
                if (obj > target) {
                    int r = right - 1;

                    while (left < r && nums[r] == nums[right]) {
                        r--;
                    }
                    right = r;
                } else {
                    int l = left + 1;
                    while ((l < right && nums[l] == nums[left])) {
                        l++;
                    }
                    left = l;

                }

            }
        }

        return bestNum;

    }

    public static void main(String[] args) {

        ThreeSumClosest threeSumClosest = new ThreeSumClosest();
        int[] nums = new int[]{-1, 2, 1, -4};
        int i = threeSumClosest.threeSumClosest(nums, 1);
        System.out.println(i);
    }
}
